package leetcode.tree_problem;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 145. 二叉树的后序遍历【迭代】
 * https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
 */
public class PostorderTraversalFunTwo {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null){
            return list;
        }
        TreeNode cur = root;
        TreeNode prev = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()){
            while (cur != null){//先一路走到最左端的操作节点
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            //这里栈顶就是最左端节点；但是以第一次为例此时只处理了左因为作为空所以出了while此时cur在待处理根节点

            //此时处理右节点了
            if (cur.right == null || prev == cur.right){
                //右为空或者右节点已经经过处理
                list.add(cur.val);
                //这部就到妙的地方了prev移到cur即可保证右子树也经过处理
                prev = cur;
                //这里cur如果不置空就会重新压入栈执行左数在第一次时死循环
                cur = null;
            }else {//走到这里说明右数没处理，此时处理又树
                //妙在哪好兄弟，此时栈顶已经变了，但是代操作节点为该树的右节点，所以要把操作节点cur重新压入栈
                stack.push(cur);
                //然后干啥，然后处理该操作节点的右节点
                cur = cur.right;//操作节点就到了他的右子树下一轮处理右子树
            }


        }
        return list;
    }
}
